{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Unique Binary Search Trees"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #binary-search-tree #math #dynamic-programming #binary-tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #二叉搜索树 #数学 #动态规划 #二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: numTrees"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #不同的二叉搜索树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个整数 <code>n</code> ，求恰由 <code>n</code> 个节点组成且节点值从 <code>1</code> 到 <code>n</code> 互不相同的 <strong>二叉搜索树</strong> 有多少种？返回满足题意的二叉搜索树的种数。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/01/18/uniquebstn3.jpg\" style=\"width: 600px; height: 148px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 3\n",
    "<strong>输出：</strong>5\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 1\n",
    "<strong>输出：</strong>1\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 <= n <= 19</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [unique-binary-search-trees](https://leetcode.cn/problems/unique-binary-search-trees/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [unique-binary-search-trees](https://leetcode.cn/problems/unique-binary-search-trees/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['3', '1']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTrees(self, n: int) -> int:\n",
    "        '''\n",
    "        combination\n",
    "        '''\n",
    "        dp = [0]*(n+1)\n",
    "        dp[0] = dp[1] = 1\n",
    "        for i in range(2, len(dp)):\n",
    "            # current root + left of root is from 1 to j\n",
    "            for j in range(1, i+1):\n",
    "                # left is j-1, 1 is current root, then the number of right nodes are i-j\n",
    "                dp[i] += dp[j-1]*dp[i-j]\n",
    "        return dp[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTrees(self, n):\n",
    "        \"\"\"\n",
    "        :type n: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        res = [0]*(n+1)\n",
    "        res[0] = 1\n",
    "        \n",
    "        for i in range(1,len(res)):\n",
    "            for j in range(i):\n",
    "                res[i]+=res[j]*res[i-1-j]\n",
    "                \n",
    "        return res[-1]\n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        # res = [0]*(n+1)\n",
    "        # res[0] = 1\n",
    "        # for i in range(1,len(res)):\n",
    "        #     for j in range(i):\n",
    "        #         res[i] +=res[j]*res[i-1-j]\n",
    "        # return res[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTrees(self, n):\n",
    "        \"\"\"\n",
    "        :type n: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if n <= 0:\n",
    "            return 0\n",
    "        \n",
    "        memo = {}\n",
    "        def helper(n):\n",
    "            if n not in memo:\n",
    "                if n <= 1:\n",
    "                    memo[n] = 1\n",
    "                else:\n",
    "                    res = 0\n",
    "                    for i in range(n):\n",
    "                        L = helper(i)\n",
    "                        R = helper(n - i - 1)\n",
    "                        res += L * R\n",
    "                    memo[n] = res\n",
    "            return memo[n]\n",
    "        return helper(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTrees(self, n):\n",
    "        \"\"\"\n",
    "        :type n: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        \n",
    "        G = [1, 1]\n",
    "        for i in range(2, n+1):\n",
    "            he = 0\n",
    "            for j in range(i // 2):\n",
    "                print(i, j)\n",
    "                he += G[j] * G[i-j-1] * 2\n",
    "            if i % 2 == 1:\n",
    "                he += G[i // 2] * G[i // 2]\n",
    "            G.append(he)\n",
    "        return G[n]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTrees(self, n):\n",
    "        \"\"\"\n",
    "        :type n: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        \n",
    "        catalan = [1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190, 6564120420, 24466267020, 91482563640, 343059613650, 1289904147324, 4861946401452]\n",
    "\n",
    "        return catalan[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTrees(self, n):\n",
    "        \"\"\"\n",
    "        :type n: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        print(self.fact(2*n))\n",
    "        print(self.fact(2))\n",
    "        print(self.fact(3))\n",
    "        print(self.fact(6))\n",
    "        return self.fact(2*n)//(self.fact(n + 1) * self.fact(n))  #2n!/((n+1)!*n!)   注意是取整乘\n",
    "        \n",
    "    def fact(self, n):   #这个结果应该是返回n的阶乘\n",
    "        if n==0:\n",
    "            return 1\n",
    "        return n * self.fact(n-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTrees(self, n: int) -> int:\n",
    "        \"\"\"\n",
    "        :type n: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        G = [0]*(n+1)\n",
    "        G[0], G[1] = 1, 1\n",
    "\n",
    "        for i in range(2, n+1):\n",
    "            for j in range(1, i+1):\n",
    "                G[i] += G[j-1] * G[i-j]\n",
    "\n",
    "        return G[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTrees(self, n: int) -> int:\n",
    "        dp = [0] * (n+1)\n",
    "        dp[0] = 1\n",
    "        dp[1] = 1\n",
    "\n",
    "        for i in range(2, n+1):\n",
    "            for j in range(1, i+1):\n",
    "                dp[i] += dp[j-1]*dp[i-j]\n",
    "        return dp[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTrees(self, n: int) -> int:\n",
    "        \n",
    "        g = [0]*(n+1)\n",
    "        g[0],g[1] = 1,1\n",
    "        if n <=1:\n",
    "            return g[n]\n",
    "        for i in range(2,n+1):\n",
    "            for j in range(1,i+1):\n",
    "                #print(g,i,j,g[j-1]*g[i-j])\n",
    "                g[i] = g[i] + g[j-1]*g[i-j]\n",
    "        return g[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTrees(self, n: int) -> int:\n",
    "        g=[0]*(n+1)\n",
    "        g[0],g[1]=1,1\n",
    "        for i in range(2,n+1):\n",
    "            for j in range(1,i+1):\n",
    "                g[i]+=g[j-1]*g[i-j]\n",
    "        return g[n]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTrees(self, n: int) -> int:\n",
    "        if n <= 2:\n",
    "            return n\n",
    "        dp = [0 for _ in range(n+1)]\n",
    "        dp[0], dp[1], dp[2] = 1, 1, 2\n",
    "        for i in range(3, n+1):\n",
    "            for j in range(i):\n",
    "                dp[i] = dp[i] + dp[j] * dp[i-j-1]\n",
    "        return dp[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTrees(self, n: int) -> int:\n",
    "        \"\"\"\n",
    "        :type n: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        C = 1\n",
    "        for i in range(0, n):\n",
    "            C = C * 2*(2*i+1)/(i+2)\n",
    "        return int(C)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTrees(self, n: int) -> int:\n",
    "        # 直接递归，超时\n",
    "        # 加 备忘录\n",
    "        memo = {}\n",
    "        res = 0\n",
    "        if n <= 1:\n",
    "            return 1\n",
    "        for i in range(1, n + 1):\n",
    "            if (i - 1) not in memo:\n",
    "                memo[i - 1] = self.numTrees(i - 1)\n",
    "            if (n - i) not in memo:\n",
    "                memo[n - i] = self.numTrees(n - i)\n",
    "            res += memo[i - 1] * memo[n - i]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTrees(self, n: int) -> int:\n",
    "        dp=[0 for i in range(0,n+1)]\n",
    "        dp[0] = 1\n",
    "        dp[1] = 1\n",
    "        for i in range(2,n+1): # 2,3\n",
    "            for j in range(0,i):\n",
    "                dp[i] = dp[0+j]*dp[i-1-j] + dp[i]\n",
    "        return dp[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTrees(self, n: int) -> int:\n",
    "        if n < 3:\n",
    "            return n \n",
    "\n",
    "        dp = [0 for i in range(n+1)]\n",
    "        dp[0] = 1\n",
    "        dp[1] = 1\n",
    "\n",
    "        for i in range(2, n+1):\n",
    "            for j in range(1,i+1):\n",
    "                dp[i] += dp[j-1] * dp[i-j]\n",
    "\n",
    "\n",
    "        return dp[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    class TreeNode:\n",
    "        def __init__(self, val=0, left=None, right=None):\n",
    "            self.val = val\n",
    "            self.left = left\n",
    "            self.right = right\n",
    "\n",
    "    def numTrees(self, n: int) -> int:\n",
    "        res_dict = {}\n",
    "        right_dict = {}\n",
    "        def dfs(vals):\n",
    "            if len(vals) == 0:\n",
    "                return 1\n",
    "            # trees = []\n",
    "            trees_num = 0\n",
    "            for i in range(len(vals)):\n",
    "                if tuple(vals[:i]) in res_dict:\n",
    "                    lefts = res_dict[tuple(vals[:i])]\n",
    "                else:\n",
    "                    lefts = dfs(vals[:i])\n",
    "                    res_dict[tuple(vals[:i])] = lefts\n",
    "\n",
    "                if tuple(vals[i+1:]) in right_dict:\n",
    "                    rights = right_dict[tuple(vals[i+1:])]\n",
    "                else:\n",
    "                    rights = dfs(vals[i+1:])\n",
    "                    right_dict[tuple(vals[i+1:])] = rights\n",
    "                rights = dfs(vals[i+1:])\n",
    "\n",
    "                # lefts = dfs(vals[:i])\n",
    "                # rights = dfs(vals[i+1:])\n",
    "\n",
    "                print(lefts*rights)\n",
    "                trees_num += lefts * rights\n",
    "\n",
    "                # for left in lefts:\n",
    "                #     for right in rights:\n",
    "                #         root = TreeNode(vals[i])\n",
    "                #         root.left = left\n",
    "                #         root.right = right\n",
    "                #         trees.append(root)\n",
    "                # res_dict[i] = lefts*rights #以i为根节点的就这么多\n",
    "            return trees_num\n",
    "        \n",
    "\n",
    "        vals_list = [i for i in range(1, n+1)]\n",
    "        return dfs(vals_list)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTrees(self, n: int) -> int:\n",
    "        totalNum = 0\n",
    "        memo = {}\n",
    "        def computeHead(start,head,end):\n",
    "            if (start,head,end) in memo:\n",
    "                return memo[(start,head,end)]\n",
    "            if head>end:\n",
    "                return 0\n",
    "            leftNum,rightNum = 0,0\n",
    "            for i in range(start,head):  #从head-1个里面选一个作为左子树头节点\n",
    "                leftNum += computeHead(start,i,head-1)\n",
    "            for i in range(head+1,end+1):\n",
    "                rightNum += computeHead(head+1,i,end)\n",
    "            leftNum = leftNum if leftNum!=0 else 1\n",
    "            rightNum = rightNum if rightNum!=0 else 1\n",
    "            memo[(start,head,end)] = leftNum*rightNum\n",
    "            return leftNum*rightNum\n",
    "        for i in range(1,n+1):\n",
    "            totalNum+=computeHead(1,i,n)\n",
    "        return totalNum\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTrees(self, n: int) -> int:\n",
    "        C = 1\n",
    "        for i in range(0, n):\n",
    "            C = C * 2*(2*i+1)/(i+2)\n",
    "        return int(C)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTrees(self, n: int) -> int:\n",
    "        dp = [0] * (n + 1)\n",
    "        dp[0], dp[1] = 1, 1\n",
    "        for i in range(2, n + 1):\n",
    "            for j in range(i):\n",
    "                dp[i] += dp[j] * dp[i - 1 - j]\n",
    "        return dp[-1]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTrees(self, n: int) -> int:\n",
    "        dp = [0] * (n+1)\n",
    "        dp[0] = 1\n",
    "        dp[1] = 1\n",
    "        for i in range(2, n+1):\n",
    "            for j in range(i):\n",
    "                dp[i] += dp[j]*dp[i-j-1]\n",
    "            print(dp)\n",
    "        return dp[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTrees(self, n: int) -> int:\n",
    "        dp = [0] * (n+1)\n",
    "        dp[0] = 1\n",
    "        dp[1] = 1\n",
    "        # dp[2] = 2\n",
    "        for i in range(2,n+1):\n",
    "            for j in range(1,n+1):\n",
    "                dp[i] += dp[j-1] * dp[i-j]\n",
    "        return dp[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTrees(self, n: int) -> int:\n",
    "\n",
    "        # '1 <= n <= 19', ...;\n",
    "        # (...); \n",
    "\n",
    "        # [没有'接上面'(...)的, ...]; \n",
    "        # [只能'往下'(...)接, ...]; \n",
    "        # (...); \n",
    "\n",
    "        # 'dp[0]'(可能)(...)很重要(辅助)(...); \n",
    "        # (...); \n",
    "\n",
    "        # {想想是'乘'(...)的关系, [还是'加'(...)的关系](还是'...), ...}; \n",
    "        # (...); \n",
    "\n",
    "        # node(不接), ...;\n",
    "        # node接一个, ...;\n",
    "        # node接两个, ...;\n",
    "        # node接三个, ...;\n",
    "        # (...); \n",
    "\n",
    "        # [这些情况都要加(考虑)(...)上, ...]; \n",
    "        # (...); \n",
    "\n",
    "        dp = [0] * (n + 1)\n",
    "\n",
    "        dp[0] = 1\n",
    "        dp[1] = 1\n",
    "\n",
    "        for i in range(2, n + 1):\n",
    "            for j in range(0, i): \n",
    "                print(j, i - j - 1)\n",
    "                dp[i] += dp[j] * dp[i - j - 1]\n",
    "\n",
    "        # {这个'dp'(...)累计了之前所有的, [并且还有'关系'('乘')('加')('...'), ...], ...};\n",
    "        # (...); \n",
    "\n",
    "        print(dp)\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTrees(self, n: int) -> int:\n",
    "        # 递归，以某个节点为根，其余节点的排列组合，根节点可切割整个序列\n",
    "        # 像是动态规划\n",
    "        def dfs(n):\n",
    "            if n < 2:\n",
    "                return 1\n",
    "            # dfs(1, k-1) + dfs(k+1, n)\n",
    "            # if n // 2: # 奇数\n",
    "            #     res = 2*(dfs(n-1) + dfs(n-2)*dfs(1) + ... + ) + dfs(n//2)*dfs(n//2)\n",
    "            # else:\n",
    "            #     res = 2* (dfs(n-1) + dfs(n-2)*dfs(1) + ... + dfs(n//2-1)*dfs(n//2))\n",
    "            print(n//2)\n",
    "            if n%2==1:\n",
    "                res = 0\n",
    "                for i in range(n//2):\n",
    "                    res += 2*dfs(i)*dfs(n-1-i)\n",
    "                    # print('b ', res)\n",
    "                res += dfs(n//2)*dfs(n//2)\n",
    "            else:\n",
    "                res = 0\n",
    "                for i in range(n//2):\n",
    "                    res += 2*dfs(i)*dfs(n-1-i)\n",
    "                    # print('aa ',res)\n",
    "            return res\n",
    "\n",
    "        return dfs(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTrees(self, n: int) -> int:\n",
    "        dp = [0] * (n + 1)\n",
    "        dp[0] = 1\n",
    "        dp[1] = 1\n",
    "        for i in range(2, n + 1):\n",
    "            for j in range(1, i + 1):\n",
    "                dp[i] += dp[i - j] * dp[j - 1]\n",
    "        return dp[n]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTrees(self, n: int) -> int:\n",
    "        '''\n",
    "        节点数目确定的情况下，二叉搜索树的种数是确定的；\n",
    "        i个节点的情况下，当j为根节点时，所有二叉搜索树的集合是左子树集合和右子树集合的笛卡尔积，左子树与右子树的节点数目为(j - 1)和(i - j)；\n",
    "        i的取值为[1, n], j的取值范围为[1, i]\n",
    "        运用动态规划dp[i]表示i个节点的二叉搜索树数量\n",
    "        '''\n",
    "        dp = [0] * (n + 1)\n",
    "        dp[0] = 1\n",
    "        for i in range(1, n + 1):\n",
    "            for j in range(1, i + 1):\n",
    "                dp[i] += dp[j - 1] * dp[i - j]\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTrees(self, n: int) -> int:\n",
    "        numdict={0:1}\n",
    "        def treenums(nums):\n",
    "            if not nums:\n",
    "                return 1\n",
    "            r=0\n",
    "            for i in range(nums):\n",
    "                if i in numdict:\n",
    "                    left=numdict[i]\n",
    "                else:\n",
    "                    left=treenums(i)\n",
    "                    numdict[i]=left\n",
    "                if nums-i-1 in numdict:\n",
    "                    right=numdict[nums-i-1]\n",
    "                else:    \n",
    "                    right=treenums(nums-i-1)\n",
    "                    numdict[nums-i-1]=right\n",
    "                r+=left*right\n",
    "            return r\n",
    "        return treenums(n)\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
